#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;

/*
递归版归并排序
*/
void merge_sort(vector<int> &v,vector<int> t,int l,int r){
    if(l >= r) return;
    int len=r-l,mid=(len>>1)+l;
    int l1=l,r1=mid;
    int l2=mid+1,r2=r;
    merge_sort(v,t,l1,r1);
    merge_sort(v,t,l2,r2);
    int k=l;
    while(l1<=r1 && l2<=r2)
        t[k++]=v[l1]<v[l2]?v[l1++]:v[l2++];
    while(l1<=r1)
        t[k++]=v[l1++];
    while(l2<=r2)
        t[k++]=v[l2++];

    for(k=l;k<=r;k++)
        v[k]=t[k];
}

/*
迭代版的归并排序
没写出来
*/
// void merge_sort2(vector<int> &v){
//     int len=v.size();
//     vector<int> tmp(len,0);
//     for(int seg=1;seg<len;seg+=seg){
//         for(int l=0;l<len;l+=seg*2){
//             int i=l,m=min(l+seg,len),j=min(l+2*seg,len);
//             int k=i;
//             int l1=i,r1=m;
//             int l2=m+1,r2=j;
//             while(l1<=r1 && l2<=r2)
//                 tmp[k++]= v[l1]<v[l2]?v[l1++]:v[l2++];
//             while(l1<=r1) tmp[k++]=v[l1++];
//             while(l2<=r2) tmp[k++]=v[l2++];
//             for(int x=i;x<=j;x++){
//                 v[x]=tmp[x];
//             }
//         }
//     }
//     v.swap(tmp);
// }

void msort(vector<int> &v){
    vector<int> t(v.size()+1,0);
    //merge_sort2(v);
   merge_sort(v,t,0,v.size()-1);
}

int main(){
    vector<int> v={65,45,67,89,6,54,78,312,35,5687,689,3546,68};


    msort(v);
    for(auto x:v){
        cout << x <<" ";
    }cout <<endl;

    return 0;
}